#include"Heap.h"

void Swap(HPDataType* a, HPDataType* b) {
	HPDataType temp = *a;
	*a = *b;
	*b = temp;
}


void AdjustUp(Heap* hp) {
	assert(hp);
	int child = hp->_size - 1;
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (hp->_a[child] > hp->_a[parent])
		{
			Swap(&hp->_a[child], &hp->_a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
			break;
	}
}

void AdjustDown(Heap* hp) {
	assert(hp);
	
	int child = 1;
	int parent = 0;
	while (child < hp->_size)
	{
		if ((child+1)<hp->_size&&hp->_a[child] < hp->_a[child + 1])
			++child;
		if (hp->_a[parent] < hp->_a[child])
		{
			Swap(&hp->_a[child], &hp->_a[parent]);
			parent = child;
			child = 2 * child + 1;
		}
		else
			break;
	}
}


void HeapCreate(Heap* hp, HPDataType* a, int n) {
	assert(hp);
	hp->_a = NULL;
	hp->_capacity = 0;
	hp->_size = 0;
	while (n--)
	{
		HeapPush(hp, *a++);
	}
}



void HeapDestory(Heap* hp) {
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
}


void HeapPush(Heap* hp, HPDataType x) {
	assert(hp);
	if (hp->_size == hp->_capacity)
	{
		size_t newcapacity = hp->_capacity == 0 ? 4 : 2 * hp->_capacity;
		Heap* temp = (Heap*)realloc(hp->_a, sizeof(Heap) * newcapacity);
		assert(temp);
		hp->_a = temp;
		hp->_capacity = newcapacity;
	}
	hp->_a[hp->_size] = x;
	hp->_size++;
	AdjustUp(hp);
}


void HeapPop(Heap* hp) {
	assert(hp);
	assert(hp->_size > 0);
	Swap(&hp->_a[hp->_size - 1], &hp->_a[0]);
	hp->_size--;
	AdjustDown(hp);
	
}


HPDataType HeapTop(Heap* hp) {
	assert(hp);
	return hp->_a[0];
}

int HeapSize(Heap* hp) {
	assert(hp);
	return hp->_size;
}

int HeapEmpty(Heap* hp) {
	assert(hp);
	return !hp->_size;
}